'''
Created on Aug 27, 2009

@author: echeek
'''

import math

CALLERS=1000000;

lfgindex=0;
lfgbuff=[0]*55;

# [100003 - 200003k + 300007k3] (modulo 1000000)
for i in range(len(lfgbuff)):
    lfgbuff[i]=(100003 - 200003*(i+1) + 300007*(i+1)**3)%CALLERS;

def numGen():
    global lfgindex;
    lfgindex+=1;
    if( lfgindex<= 55):
        return lfgbuff[lfgindex-1];
    val=(lfgbuff[-24]+lfgbuff[-55])%CALLERS;
    lfgbuff.append(val);
    lfgbuff.remove(lfgbuff[0]);
    return val;




groups=[-1]*CALLERS;
groupsizes=[1]*CALLERS;

def find(x):
    g=x;
    #find
    while groups[g]>-1:
        g=groups[g];
    
    #compress paths
    while groups[x]>-1:
        next=groups[x];
        groups[x]=g;
        x=next;
        
    return g;

def union(a,b):
    ga=find(a);
    gb=find(b);
    
    if(ga==gb):
        return;
    
    if( groups[ga] > groups[gb] ): #ga tree is shorter
        swap=ga;
        ga=gb;
        gb=swap;
    
    bheight=groups[gb];
    groups[gb]=ga;
    groups[ga]=min(bheight-1,groups[ga]);
    groupsizes[ga]+=groupsizes[gb];
    
    
primeminister=524287;
def Euler186():
    callcount=0;
    percent=0;
    while percent<0.99:
        caller=numGen();
        called=numGen();
        if(caller==called):
            continue;
        callcount+=1;
        union(caller, called);
        percent=(groupsizes[find(primeminister)]/float(CALLERS))
        
    print callcount;
    
Euler186();